﻿#include<iostream>
#include<iomanip>
#include<strstream>
using namespace std;
typedef struct BiTNode 
{
	char data;
	struct BiTNode* lchild, * rchild;
	BiTNode(char in) : data(in), lchild(NULL), rchild(NULL) { };
}BiTNode, * BiTree;
void PrintBtree(BiTree BT);
BiTNode* createBiTree() //创建二叉链表一递归算法 
{
	int ch;
	BiTNode* BT;
	ch = getchar();
	if (ch == '#')
	{
		return NULL;
	}
	else
	{
		BT = (BiTNode*)malloc(sizeof(BiTNode));
		BT->data = ch;
		BT->lchild = createBiTree();
		BT->rchild = createBiTree();

	}
	return BT;
}
void InOrder(BiTree BT) //中序遍历递归
{
	if (BT != NULL) {
		InOrder(BT->lchild);
		cout << BT->data;
		InOrder(BT->rchild);
	}
}
void PrintBtree(BiTree BT)
{  //按二叉树广义表方式输出
	if (BT != NULL) {
		cout << BT->data;
		if (BT->lchild || BT->rchild) {
			cout << '(';
			PrintBtree(BT->lchild);
			if (BT->rchild)
				cout << ',';
			PrintBtree(BT->rchild);
			cout << ')';
		}
	}
}
int height(BiTree T)/*求树高*/
{
		int i, j;
		if (!T) return 0;
		i = height(T->lchild);/*求左子树的高度*/
		j = height(T->rchild); /* 求右子树的高度*/
		return i > j ? i + 1 : j + 1;
		/*二叉树的高度为左右子树中较高的高度加1*/
}

	
int leafs(BiTNode* T) /* 求叶子结点数*/
{
	int n1, n2;
	if (T == NULL) return 0;
	else
	{
		if (T->lchild == NULL && T->rchild == NULL) return 1;
		n1 = leafs(T->lchild);//求左子树中叶子结点数
		n2 = leafs(T->rchild); //求右 子树中叶子结点数
		return n1 + n2;
	}
}
BiNode* exchange(BiNode* root)
{
	BiNode* temp;
	if (root->lchild == NULL && root->rchild == NULL)
		return  root;
	else {
		temp = root->lchild;
		root->lchild = root->rchild;
		root->rchild = temp;
	}
	if (root->lchild)
		exchange(root->lchild);
	if (root->rchild)
		exchange(root->rchild);
	PrintBtree(root);
	return root;
}

int main()
{
	BiTNode* r;
	r = NULL;
	cout << "请输入结点的前序序列创建二叉树: #表示空: " << endl;
	r=createBiTree();
	cout << "以广义表的形式输出：" << endl;
	PrintBtree(r);
	cout << endl;
	cout << "中序递归遍历：" << endl; 
	InOrder(r);
	cout << endl;
	cout << "二叉树高度：" << height(r) << endl;
	cout << endl;
	cout << "二叉树中叶子结点数为: " << leafs(r) << endl;
	cout << "二叉树左右子树交换后以广义表形式输出：" << endl;
	exchange(r);
	return 0;
}